public class Solution63 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid[0][0]==1){
            return 0;
        }
        int m=obstacleGrid.length,n=obstacleGrid[0].length;
        int[][] f=new int[m][n];
        f[0][0]=1;
        for (int i=1;i<m;i++){
            f[i][0]=f[i-1][0];
            if (obstacleGrid[i][0]==1){
                f[i][0]=0;
            }
        }
        for (int i=1;i<n;i++){
            f[0][i]=f[0][i-1];
            if (obstacleGrid[0][i]==1){
                f[0][i]=0;
            }
        }
        for (int i=1;i<m;i++){
            for (int j=1;j<n;j++){
                if (obstacleGrid[i][j]!=1){
                    f[i][j]=f[i-1][j]+f[i][j-1];
                }
            }
        }
        return f[m-1][n-1];
    }

    public static void main(String[] args) {
        System.out.println(new Solution63().uniquePathsWithObstacles(new int[][]{{0,0,0},{0,1,0},{0,0,0}}));
    }
}
